// https://leetcode.cn/problems/three-equal-parts/
// Created by ade on 2022/10/10.
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> threeEqualParts(vector<int> &arr) {
        int c = count_if(arr.begin(), arr.end(), [](int i){return i == 1;});
        if (c % 3 != 0) return {-1, -1};
        if (c == 0) return {0, 2};

        int first = 0, third = 0, thirdLen = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] == 1) {
                first = i;
                break;
            }
        }
        int count = 0;

        for (int i = arr.size() - 1; i >= 0; i--) {
            if (arr[i] == 1) count++;
            if (count == c / 3) {
                third = i;
                thirdLen = arr.size() - third;
                break;
            }
        }
        for (int i = first; i < first + thirdLen; i++) {
            if (arr[i] != arr[third + i - first]) return {-1, -1};
        }
        int second = 0;
        for (int i = first + thirdLen; i < third; i++) {
            if (arr[i] == 1) {
                second = i;
                break;
            }
        }
        for (int i = second; i < second + thirdLen; i++) {
            if (arr[i] != arr[third + i - second]) return {-1, -1};
        }

        // 注：second不包括
        return {first + thirdLen - 1, second + thirdLen};
    }
};

int main() {
    vector<int> nums = {1, 1, 0, 0, 1};
    Solution so;
    auto a = so.threeEqualParts(nums);
    cout << a[0] << "," << a[1] << endl;
    return 0;
}